package java;

import java.util.HashMap;
import java.util.Map;

/**
 * 力扣146. LRU 缓存
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
 * 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 *
 * 第一中方式是继承LinkedHashMap,重写removeEldestEntry方法来达成想要的效果，显然这个方法不推荐
 *
 *
 * 我这边类名叫MyLinkedHashMap,原本的LinkedHashMap有这个功能
 * @author HuWLin
 *
 * */


public class MyLinkedHashMap {
    //内部类，存放基本信息
    class Node {
        public int key;
        public int value;
        public Node prev;
        public Node next;
        public Node(){
        }
        public Node(int _key,int _value) {
            key = _key;
            value = _value;
        }
    }
    //head用来存放头，空的，tail用来存放尾也是空的
    //头部为使用过的，尾部为最少使用的
    public Node head,tail;
    //存入基本信息
    public Map<Integer,Node> map = new HashMap<>();
    //size存放大小，capacity存放最大长度
    public int size,capacity;

    public MyLinkedHashMap(int capacity) {
        size = 0;
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if(node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if(node == null) {
            //首次添加都添加到最前面
            Node tmp = new Node(key,value);
            addToHead(tmp);
            map.put(key,tmp);
            size ++;
            if(size > capacity) {
                //若大于最大长度，则把链表最后的一个删了，并且把map里的数据也删了
                map.remove(removeLast().key);
            }
        }else {
            node.value = value;
            map.put(key,node);
            //若之前存在数据，数据修改过移动到最前面
            moveToHead(node);
        }
    }

    //移动到头部的思路，删除链表当前结点，把此节点添加到头部
    public void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    //删除node结点
    public void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    //将node结点放入头部
    public void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    //删除最后一个结点
    public Node removeLast() {
        //最后一个结点也就是tail的前一个，tail不存数据，仅仅是尾结点
        Node node = tail.prev;
        removeNode(node);
        return node;
    }

}
